package ACM_Brush;

import java.util.Random;

public class Sort {
    public static void main(String[] args) {
        int[] array = new int[] { 1, -1, 10, 3, 6, 99, 37, 51, 77, 62, -76, -22 };
        // bubbleSort(array);
        // quickSort(array, 0, array.length - 1);
        // selectSort(array);
        // insertSearch(array);
        // mergeSort(array, 0, array.length - 1);
        // heapSort(array);
        quickSortv2(array, 0, array.length - 1);
        for (int i = 0; i < array.length; i++)
            System.out.println(array[i]);
    }

    private static void bubbleSort(int[] array) {
        int length = array.length;
        for (int i = 0; i < length - 1; i++)
            for (int j = 0; j < length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
    }

    private static void quickSort(int[] array, int left, int right) {
        int i = left, j = right;
        if (i >= j)
            return;
        int pivot = array[i];
        while (i < j) {
            while (i < j && array[j] >= pivot)
                j--;
            array[i] = array[j];
            while (i < j && array[i] <= pivot)
                i++;
            array[j] = array[i];
        }
        array[i] = pivot;
        quickSort(array, left, i - 1);
        quickSort(array, i + 1, right);
    }

    private static void quickSortv2(int[] nums, int left, int right){
        if(left >= right)
            return;
        int l = left, r = right;
        int pivot = left + new Random().nextInt(right - left);
        int i = left;
        while(i <= r){
            if(nums[i] < nums[pivot]){
                int temp = nums[i];
                nums[i] = nums[l];
                nums[l] = temp;
                l++;
                i++;
            }else if(nums[i] > nums[pivot]){
                int temp = nums[i];
                nums[i] = nums[r];
                nums[r] = temp;
                r--;
            }else{
                i++;
            }
        }
        quickSortv2(nums, left, l - 1);
        quickSortv2(nums, r + 1, right);
    }

    private static void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex])
                    minIndex = j;
            }
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }

    private static void insertSearch(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] > temp) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = temp;
        }
    }

    private static void mergeSort(int[] array, int left, int right) {
        if (left >= right)
            return;
        int mid = left + (right - left) / 2;
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);
        merge(array, left, mid, right);
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int[] tempArray = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            tempArray[k++] = array[i] < array[j] ? array[i++] : array[j++];
        }
        while (i <= mid) {
            tempArray[k++] = array[i++];
        }
        while (j <= right) {
            tempArray[k++] = array[j++];
        }
        for (int m = 0; m < tempArray.length; m++) {
            array[left + m] = tempArray[m];
        }
    }

    private static void heapSort(int[] array) {
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            heapify(array, array.length, i);
        }
        for (int i = array.length - 1; i >= 0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            heapify(array, i, 0);
        }
    }

    private static void heapify(int[] array, int n, int i) {
        int largest = i;
        int l = i * 2 + 1, r = i * 2 + 2;
        if (l < n && array[l] > array[largest])
            largest = l;
        if (r < n && array[r] > array[largest])
            largest = r;
        if (largest != i) {
            int temp = array[i];
            array[i] = array[largest];
            array[largest] = temp;
            heapify(array, n, largest);
        }
    }
}
